package com.jn.algorithm.day005.question16;

import java.util.Arrays;

/**
 * @author 江南大学1033190417
 * @date 2022/4/19 15:06
 */
public class Solution {

    //排序+双指针
    public int threeSumClosest(int[] nums, int target) {
        int best = Integer.MAX_VALUE/2;
        //排序
        Arrays.sort(nums);
        int length = nums.length;
        for (int first = 0; first < length; first++) {
            //如果已经枚举过了
            if (first > 0 && nums[first] == nums[first - 1]) {
                continue;
            }
            int third = length - 1;
            int second = first + 1;
            while (second < third) {
                int sum = nums[first] + nums[second] + nums[third];
                if (sum == target) {//如果刚好相等，直接返回
                    return target;
                }
                if (Math.abs(sum - target) < Math.abs(best - target)) {
                    best = sum;
                }
                if (sum > target) {//如果大于target，那么就把third左移，变小
                    int k = third - 1;
                    while (second < k && nums[k] == nums[third]) {//移动到第一个不相等的
                        --k;
                    }
                    third = k;
                } else {//如果大于target，那么就把second右移，变大
                    int k = second + 1;
                    while (k < third && nums[k] == nums[second]) {//移动到第一个不相等的
                        ++k;
                    }
                    second = k;
                }
            }
        }
        return best;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = new int[]{-3,-2,-5,3,-4};
        int target = -1;
        System.out.println(solution.threeSumClosest(nums, target));

    }
}
